use std::collections::BTreeSet;

pub fn goldbach_conjecture() -> u64 {
    for bit in 0.. {
        // work with a limit. this can fasten the program
        if let Some(ans) = work(1 << bit) {
            return ans;
        }
    }
    unreachable!()
}

/// cal the ans in [0, limit]
fn work(limit: u64) -> Option<u64> {
    let mut primes = Vec::new();
    let mut powers = Vec::new();
    let mut valid = BTreeSet::new();
    primes.push(2);
    let mut ans = 0;
    for now in 1..=limit {
        // update as power
        update(2 * now * now, &primes, &mut valid, limit);
        powers.push(2 * now * now);
        if now == 1 || (now & 1) == 0 {
            let _ = valid.remove(&now);
            continue;
        }
        // update as prime
        if is_prime(now) {
            update(now, &powers, &mut valid, limit);
            primes.push(now);
        }
        // check ans
        else if !valid.contains(&now) {
            if ans == 0 {
                ans = now;
            } else {
                return Some(ans + now);
            }
        }
        let _ = valid.remove(&now);
    }
    None
}

fn is_prime(n: u64) -> bool {
    let limit = (n as f64).sqrt() as u64;
    for x in 2..=limit {
        if (n / x) * x == n {
            return false;
        }
    }
    true
}

/// add `num` to every element in the `arr`, insert the result in the `valid`
fn update(num: u64, arr: &Vec<u64>, valid: &mut BTreeSet<u64>, limit: u64) {
    for x in arr {
        let sum = num + x;
        if sum > limit {
            break;
        }
        valid.insert(sum);
    }
}
